The layout of a page or graphic image depends upon combining “structured graphics” according to a pre-established graphic design. The structured graphics are contiguous regions of color, usually represented in a plurality of separation images, in turn representing a succession of graphic objects imaged on the printing medium (e.g., the “paper”). The objects so imaged are shapes which can be: isolated from each other, abut one another at one or more points, partially overlap one another, or completely overlap one another. The resulting printed page or graphic image is therefore made up of a patchwork of shapes representing the graphic objects, some of which are “clipped” (or hidden) by objects imaged later in the succession.
The result of abutting or overlapping shapes is a boundary between adjacent regions of color which, under ideal printing conditions, should have zero width. That is, the one color should stop exactly where the other begins with no new colors introduced along the boundary by the printing process itself. The “colors” which fill the shapes can be solid colors, tints, degrades, contone images, or “no fill” (i.e., the paper with no ink applied). In general, the “colors” represented in these adjacent regions are printed using more than one colorant. In practice therefore, the realization of a zero width boundary between regions of different color is impossible as a result of small but visible misregistration problems from one printed separation to another. The error is manifested as a “light leak” or as a visible boundary region of an undesired color.
As an example, FIG. 1A illustrates an ideal boundary between a red region on the right and a cyan region on the left, red being composed of a combination of magenta and yellow colorant, while FIG. 1B illustrates a non-ideal boundary, resulting from a slight misregistration of the magenta separation to the left on the page. Between the red and cyan regions is formed a blue line, from the unintended combination of cyan and magenta. On the right-hand side of the red region will be formed a yellow line, again resulting from a slight misregistration of the magenta separation to the left on the page.
The problem of misregistration is a mechanical problem almost always existing in printing systems. The problem arises because color separations are not laid exactly where intended, due to inherent imperfections in any separation registration process. It is somewhat correctable by mechanical registration methods; however, it is rarely completely correctable. In expensive, high end printing processes, customers have high expectations that misregistration artifacts will not be visible. In inexpensive, low end printers, mechanical registration techniques are so expensive as to make correction or trapping essential.
Methods for correcting this misregistration are known. The general approach is to expand one of the abutting regions' separations to fill the gap or misregistration border region with a color determined to minimize the visual effect when printed. Borders or edges expanded from a region of one color to another in this manner are said to be “spread”. A border which has been expanded is referred to as a “trap”, and the zone within which color is added is called the “trap zone”.
Commonly used methods for automatic trapping of digital images fall into the categories of vector-based and raster-based methods. Vector-based methods rely on images that have been converted from a page-description language form, describing objects as characters, polygonal shapes, etc., into an internal data structure containing not only object information, but also a list of all the edges between regions of different color. Raster-based methods rely on images that have been first scanned or converted from page-description based form and are stored internally as a sequence of (high resolution) scan lines each containing individual scan elements or pixels. These methods process each raster line in sequence and compare one or more adjacent pixels to determine color boundaries. After some initial processing to find edges, both vector-based and raster-based methods apply rules for determining whether or not to create a trap at such boundaries, and finally apply a second set of rules to determine the nature of the trap if one is to be created.
FIG. 2 illustrates a high-level flow chart of operations depicting the basic prior art basic method 100 of trapping. In general, the trap process begins, as shown at block 102 in FIG. 2. It can be seen from FIG. 2 that most trapping processes take the following format which shall be referenced throughout this discussion. Following processing of the operation shown in block 102, an operation can be implemented to find an edge in the image, no matter how described. Then, as shown at decision block 105, a step can be performed to determine if the edge has been found. If not, then the process terminates, as depicted at block 107. If so, the process continues, as depicted next at decision block 106.
As shown in decision block 106 a test can be performed to determine if a trap should be inserted. If so, then the operations continue as shown next at block 108. If not (“No”), then the operation depicted at block 104 (i.e., find an edge) can be implemented again, followed by the operations illustrated at block 105 and so on. Assuming a “Yes” result with resect to the operation depicted at block 106, then an operation can be performed to determine the trap color, as described at block 108.
Following processing of the operation for determining the trap color (i.e., block 108), an operation can be implemented to determine the trap position. Assuming “Yes” result with respect to block 110, then an operation can be implemented, as shown at block 112, to modify the image.
Thereafter, the process shown at block 104 (i.e., find an edge) can be repeated and so forth.
It can thus be appreciated that a number of methods exist for computing the “traps” needed to compensate for misregistration of printing devices. Typically, the methods are partitioned into three independent steps: identifying boundaries from one colored region to another, determining whether a “trap” placed on that boundary would improve the appearance of the document in the face of expected mechanical misregistration, and inserting the trap into the page. The disclosed embodiments, however, are primarily concerned with the second step.
Many approaches to determining an appropriate trap color are very time consuming and best suited for applications where performance is not critical. Where performance is important, optimizations such as interpolated table-lookup have been used. One prior art approach is disclosed in U.S. Pat. No. 6,345,117 (Klassen), which is incorporated by reference herein and describes a method to automatically determine, given two input colors that are spatially adjacent, whether trapping would be beneficial, the best color to use for a trap, and where to place the trap with respect to the edge between the two input colors. The algorithm described in the Klassen patent involves considerable calculation and is not directly useable in high-speed digital printing. However, it is well-suited to prepopulate an interpolated table.
The number of interpolation nodes needed in a table, however, increases very quickly as additional dimensions of color (i.e., additional process separations) are added, necessitating significantly increased memory, or a reduction in the number of nodes per dimension (which reduces accuracy) or both, and a great increase in the calculations necessary to fill all the interpolation nodes.
As an example, the current FFPS interpolated trapping table supports 4-color separations, giving it eight independent color inputs (c, m, y, and k for each of the two colors across the boundary). A future product intends to support six process colors, which would mean extending the trapping table to 12 dimensions. Even just four nodes per dimension would require over 16 million nodes to be calculated or otherwise derived, stored, and accessed.
The use of multidimensional interpolated lookup tables is a well-known practice for color conversions, and several variants exist, including trilinear and tetrahedral interpolation. These techniques have also been extended to more than three or four dimensions, including in the current FFPS interpolated trapping table, which is an 8-dimension interpolated table.